During the 1960s, the West increasingly focused on low-level strike tactics that stood to be highly effective in penetrating Soviet air defenses. In response, the Soviets invested a great deal of effort in building up those defenses. After considering a number of different options, in 1968 work was authorized on a follow-on to the MiG-25 interceptor series.

The improved machine was to provide a general increase in capability and effectiveness over the Foxbat. The Mikoyan OKB considered more radical designs to meet the requirement early on, including swing wing and delta wing configurations, but decided that it would be more effective to retain the basic arrangement of the MiG-25, and give it a thorough workover.

The OKB's investigation led to an order for full development and two prototypes, with the design effort conducted by a team under the Mikoyan OKB's Gleb Lozino-Lozinsky, and the prototypes built in the OKB workshops. The first "Ye-155MP" prototype performed its initial flight on 16 September 1975, with Fedotov at the controls, and the second followed in May 1976.

Viktor Belenko mentioned the new machine during his debriefing by Western intelligence, describing a "Super Foxbat", with two seats, a strengthened fuselage for low-altitude flight, and a powerful look-down / shoot-down radar. Exaggerated details leaked in the Western press led to a best-selling technothriller novel, Craig Thomas's FIREFOX, involving a Soviet super-fighter with Mach 3 performance, vertical takeoff capability, and direct mind control over aircraft systems; the novel led in turn to one of the worst movies Clint Eastwood ever made.

Work on what would become a total of eight preproduction machines began at the factory in Gorky in 1977. In 1978, a US spy satellite observed one of the evaluation machines, flying at 6,000 meters (20,000 feet), intercepting a target drone emulating a cruise missile flying at 60 meters (200 feet) and 20 kilometers (12.5 miles) away. That was impressive, though since the Soviets were perfectly aware of the orbital schedules of American spy satellites, it suggests the whole thing was a staged "photo-opportunity".

Trials continued into 1980, leading to a formal authorization in 1981 of full production of what was originally to be designated the "MiG-25MP" but emerged as the "MiG-31". The type entered front-line PVO service in 1982, replacing the Tu-128 Fiddler. Aircrew were impressed by the MiG-31's sophistication, range, speed, and said it could climb "like a rocket". Like the MiG-25 before it, the MiG-31 was not very maneuverable, but there was really no need for it to be.

NATO assigned the MiG-31 the reporting name "Foxhound". The West finally got good pictures of the MiG-31 in 1985, when a Norwegian pilot intercepted one over the Barents Sea and took some shots of it. That was almost certainly a photo-opportunity, the Soviets having long used such intercepts as a means of unveiling new aircraft to the West, with the aircraft turning back for home the moment the photo session was over.

A total of about 500 MiG-31s was built by the factory at Gorkiy up to the fall of the USSR. There were several minor and proposed Foxhound modifications and variants:
One early MiG-31 was used for test duties at the Zhukovsky flight center, and given the designation of "MiG-31LL", the "LL" being a common suffix for Soviet trials aircraft, standing for the Russian acronym of "flying laboratory".

Two specialized MiG-31s were built in 1987 as carriers for an antisatellite (ASAT) missile, in imitation of a contemporary US ASAT program that used a McDonnell Douglas F-15. These two Foxhounds featured triangular "webbed feet" wing endplate fins, like those fitted to some MiG-25 prototypes, in this case intended to provide improved flight stability at high altitudes for missile launches. A single large missile was to be carried under the fuselage, and a special upward-looking radar and associated intercept fire-control system was to be fitted to production machines. The cannon was deleted.

The effort was suspended in the early 1990s -- one reason, aside from the social chaos in Russia at the time, likely being the fact that attempts to build ASAT weapons have traditionally bogged down once the realization sinks in that shooting down the other side's satellites simply invites retaliation in kind. These aircraft were given the designation of "MiG-31D", which is also confusingly sometimes applied to initial production MiG-31s with refueling probes, as well as to a bewildering range of other Foxhound variants, both real and imaginary. For simplicity, this ASAT launcher is the only Foxhound variant referred to as the MiG-31D in this document.

The MiG-31D was resurrected in the late 1990s as the "MiG-31A" proposal, with the aircraft being used to launch a small satellite payload of up to 100 kilograms (220 pounds) into orbit, instead of an ASAT interceptor. That didn't happen either and the idea went into limbo, but in 2005 a collaboration of Russian and Kazakh organizations announced that a program to perform space launches with the MiG-31 had been initiated with backing from the governments of both countries. A solid-fuel booster named the "Ishim", after a river that runs through both Russia and Kazakhstan, was to be designed and built as part of the program, with the Ishim capable of placing a 160 kilogram (350 pound) satellite into low Earth orbit. The idea was interesting, but it then disappeared.

The MiG OKB showed off a multi-role fighter variant of the MiG-31B at the Paris Air Show in 1995. This machine was designated the "MiG-31F", with "F" standing for "frontovy / front AKA tactical", and was fitted with air-to-surface weapons for the strike or particularly the SEAD role. It is unclear if this particular aircraft had avionics systems to support such weapons; it may have been a more or less conventional MiG-31B that had been "jazzed up" with them for show purposes to run the idea up a flagpole and see if anyone saluted. Nobody did.

The MiG OKB proposed a "MiG-31E" interceptor for the export market, which was essentially a MiG-31B with downgraded avionics. One or two prototypes were built. The MiG organization has come up with improved proposals for export machines, but there have been no export sales of the Foxhound.

In the mid-1980s, the MiG OKB began work on an improved interceptor variant, the "MiG-31M", which was primarily designed as a carrier for the R-37 AAM, an improved follow-on to the R-33 with an astounding range of 300 kilometers (186 miles). Seven MiG-31M prototypes were built, with the first flying in late 1985.

An improved Zaslon-M radar was fitted, along with a new IRST featuring a laser rangefinder. A new "fat" spine was fitted to the aircraft to accommodate improved avionics and increase fuel storage. At least one prototype featured wingtip pods with vertical fins for electronic systems. Large LERXes were fitted to improve high angle of attack handling; the tailfins and ventral fins were reconfigured to a degree; and an improved inflight refueling probe was designed, to be fitted to the right side of the nose of the aircraft.

Six R-39s could be carried under the fuselage in recesses, arranged as three rows of two missiles. All six could be launched in salvo and seek different targets. Four R-77 AAMs could also be carried on underwing pylons. The cannon was deleted. The cockpit was redesigned, with the front seater getting a new single-piece windscreen, and the windows for the back-seater reduced to a small panel on either side to allow him to focus his attention on his displays. Back-seat flight controls were deleted.

The MiG-31M did not enter production since the Russian state lacked the money to buy many new aircraft, and so in 1997 the MiG organization began work on a multi-role upgrade to existing MiG-31s, designated "MiG-31BM".